#ifndef _HASH_MAP_CPP
#define _HASH_MAP_CPP

#include "Share.h"

namespace
{

template<class T>
inline size_t hash_value( const T &t )
{
	return t;
}

template <>
inline size_t hash_value< std::string > ( const string &str )
{
	const char *p = str.c_str( );
	unsigned int hash = 0;

	while( *p )
	{
		hash = ( *p++ ) + ( hash << 6 ) + ( hash << 16 ) - hash;
	}

	return ( hash & 0x7FFFFFFF );
}

}

template< class KEY, class VALUE >
hash_map<KEY, VALUE>::hash_map( void )
{
	for( int i = 0; i < buckets_num_; i ++ )
	{
		buckets_[ i ].begin = buckets_[ i ].end = values_.end( );
	}
}


template< class KEY, class VALUE >
hash_map<KEY, VALUE>::~hash_map( void )
{
}

template< class KEY, class VALUE > inline
typename hash_map<KEY, VALUE>::iterator
hash_map<KEY, VALUE>::find( const KEY &k )
{
	size_t bucket = hash_value( k ) % buckets_num_;
	iterator it = buckets_[ bucket ].begin;

	if( it == values_.end( ) )
		return it;

	iterator end = buckets_[ bucket ].end;

	++end;

	while( it != end )
	{
		if( it->first == k )
			return it;

		++it;
	}

	return values_.end( );
}

template< class KEY, class VALUE > inline
void hash_map<KEY, VALUE>::erase( iterator it )
{
	size_t bucket = hash_value( it->first ) % buckets_num_;

	bool isbegin = ( buckets_[ bucket ].begin == it );
	bool isend = ( buckets_[ bucket ].end == it );

	if( isbegin && isend )
		buckets_[ bucket ].begin = buckets_[ bucket ].end =
		                               values_.end( );
	else if( isbegin )
		++buckets_[ bucket ].begin;
	else if( isend )
		--buckets_[ bucket ].end;

	value_erase( it );
}

template< class KEY, class VALUE > inline
void hash_map<KEY, VALUE>::erase( const KEY & k )
{
	iterator iter = find( k );
	if( iter != end( ) )
		erase( iter );
}

template< class KEY, class VALUE > inline
typename hash_map<KEY, VALUE>::insert_result
hash_map<KEY, VALUE>::insert( const value_type &value )
{
	KEY k = value.first;
	size_t bucket = hash_value( k ) % buckets_num_;
	iterator it = buckets_[ bucket ].begin;

	if( it == values_.end( ) )
	{
		buckets_[ bucket ].begin = buckets_[ bucket ].end =
		                               value_insert( it, value );
		return insert_result( buckets_[ bucket ].end, true );
	}

	iterator end = buckets_[ bucket ].end;
	++end;

	while( it != end )
	{
		if( it->first == k )
			return insert_result( it, false );

		++it;
	}

	buckets_[ bucket ].end = value_insert( end, value );
	return insert_result( buckets_[ bucket ].end, true );
}

template< class KEY, class VALUE > inline
typename hash_map<KEY, VALUE>::insert_result
hash_map<KEY, VALUE>::insert( const KEY &k, const VALUE &v )
{
	return insert( value_type( k, v ) );
}

template< class KEY, class VALUE > inline
typename hash_map<KEY, VALUE>::iterator
hash_map<KEY, VALUE>::value_insert( iterator it, const value_type &value )
{
	if( spares_.empty( ) )
	{
		return values_.insert( it, value );
	}
	else
	{
		spares_.front( ) = value;
		values_.splice( it, spares_, spares_.begin( ) );
		return --it;
	}
}

template< class KEY, class VALUE > inline
void hash_map<KEY, VALUE>::value_erase( iterator it )
{
	*it = value_type( );
	spares_.splice( spares_.end( ), values_, it );
}

#endif

